package 算法.搜索算法;

import java.util.*;

/**
 * @author Zhu
 * @Description
 * @create 2023-03-09
 */
public class JZ38字符串的排列 {
    //递归+回溯
    public static ArrayList<String> Permutation(String str) {
        ArrayList<String> res = new ArrayList<String>();
        if(str == null || str.length() == 0)
            return res;
        //转字符数组
        char[] charStr = str.toCharArray();
        // 按字典序排序
        Arrays.sort(charStr);
        boolean[] vis = new boolean[str.length()];
        //标记每个位置的字符是否被使用过
        Arrays.fill(vis, false);
        StringBuffer temp = new StringBuffer();
        //递归获取
        recursion(res, charStr, temp, vis);
        return res;
    }

    public static void recursion(ArrayList<String> res, char[] str, StringBuffer temp, boolean[] vis){
        //临时字符串满了加入输出
        if(temp.length() == str.length){
            res.add(new String(temp));
            return;
        }
        //遍历所有元素选取一个加入
        for(int i = 0; i < str.length; i++){
            //如果该元素已经被加入了则不需要再加入了
            if(vis[i])
                continue;
            if(i > 0 && str[i - 1] == str[i] && !vis[i - 1]) // 同一层相邻
                //如果是同一条路径的话 ， 则 arr[i]的元素 arr[i-1]一定是被访问过
                // 相邻且arr[i-1]没有被访问过， 则为同一层
                //当前的元素str[i]与同一层的前一个元素str[i-1]相同且str[i-1]没用过（剪枝  同一层相邻）
                continue;
            //标记为使用过
            vis[i] = true;
            //加入临时字符串
            temp.append(str[i]);
            recursion(res, str, temp, vis);
            //回溯
            vis[i] = false;
            temp.deleteCharAt(temp.length() - 1);
        }
    }

    //java 回溯+Set去重
    Set<String> res = new HashSet<>();
    public ArrayList<String> Permutation2(String str) {
        boolean[] visited = new boolean[str.length()];
        recursion2(str,"",visited);
        ArrayList<String> list = new ArrayList<>(res);
        Collections.sort(list);
        return list;
    }

    void recursion2(String str,String current,boolean[] visited){
        if(str.length()==current.length()){
            res.add(current);
            return;
        }
        for(int i = 0;i<str.length();i++) {
            if(!visited[i]){
                current+=str.charAt(i);
                visited[i] = true;
                recursion2(str,current,visited);
                current = current.substring(0,current.length()-1);
                visited[i] = false;
            }
        }

    }


    public static void main(String[] args) {
        ArrayList<String> abc = Permutation("aab");
        System.out.println(abc);
    }
}
